// ++++++++++++++++++++++++++++++++++++++++
// 《零基础Go语言算法实战》源码
// ++++++++++++++++++++++++++++++++++++++++
// Author:廖显东（ShirDon）
// Blog:https://www.shirdon.com/
// Gitee:https://gitee.com/shirdonl/goAlgorithms.git
// Buy link :https://item.jd.com/14101229.html
// ++++++++++++++++++++++++++++++++++++++++

package main

// Node表示二叉树中的一个节点
type Node struct {
	Data  int
	Left  *Node
	Right *Node
}

// BFS 对具有根节点 root 的二叉树进行广度优先搜索遍历，并返回根节点。 如果 root 为 nil，则 BFS 返回 nil
func BFS(root *Node) *Node {
	if root == nil {
		return root
	}

	// 创建一个哈希映射来存储树的每个级别的节点
	hashMap := make(map[int][]*Node)
	hashMap[0] = []*Node{root}
	visited := []*Node{}
	i := 0

	// 遍历哈希映射中的所有节点并将它们的子节点添加到哈希映射的下一级
	for {
		// 从哈希图中获取第 i 层节点的切片
		nodeArr, ok := hashMap[i]
		if !ok {
			break
		}

		// 遍历切片中的所有节点
		for _, node := range nodeArr {
			visited = append(visited, node)

			// 如果节点有左孩子，则将其及其右孩子添加到哈希映射的下一级
			if node.Left != nil {
				_, ok := hashMap[i+1]
				if !ok {
					hashMap[i+1] = []*Node{}
				}
				hashMap[i+1] = append(hashMap[i+1], node.Left)
				hashMap[i+1] = append(hashMap[i+1], node.Right)
			}
		}
		i += 1
	}
	// 返回根节点
	return root
}

func main() {
	root := &Node{9, nil, nil}
	node2 := &Node{2, nil, nil}
	node3 := &Node{3, nil, nil}
	node4 := &Node{4, nil, nil}
	node5 := &Node{5, nil, nil}
	node6 := &Node{6, nil, nil}
	root.Left = node2
	root.Right = node3
	node2.Left = node4
	node2.Right = node5
	node3.Right = node6
	BFS(root)
}
